In the latter half of the twentieth century, there began a phenomenon known as the information revolution. While the information revolution is a historical development broader in scope than any one event or machine, no single device has come to represent the information revolution more than the digital electronic computer. The development of computer systems has surely been a revolution. Each year, computer systems grow faster, store more data, and provide more applications to their users.
A modern computer system is an enormously complex machine, usually having many sub-parts or subsystems, each of which may be concurrently performing different functions in a cooperative, although partially autonomous, manner. Typically, the system comprises one or more central processing units (CPUs) which form the heart of the system, and which execute instructions contained in computer programs. Instructions and other data required by the programs executed by the CPUs are stored in memory, which often contains many heterogenous components and is hierarchical in design, containing a base memory or main memory and various caches at one or more levels. At another level, data is also stored in mass storage devices such as rotating disk drives, tape drives, and the like, from which it may be retrieved and loaded into memory. The system also includes hardware necessary to communicate with the outside world, such as input/output controllers; I/O devices attached thereto such as keyboards, monitors, printers, and so forth; and external communication devices for communicating with other digital systems.
Each component of a digital computer system is itself a very complex instrument, having a design hierarchy which can mimic that of the system. For example, a disk drive storage device typically contains one or more spinning disks on which data is recorded, an actuator and transducers for accessing data on the disk, a central controller which executes a control program for controlling the operation of the device, motors for driving the spinning disk and the mechanical actuator, various drivers for the motor, actuator and transducer, sense amplification electronics for reading the transducer, internal communications interfaces among the various components, and an external communications interface for communicating data with the outside world. Within any such component, further design hierarchies may exist.
Although a general-purpose computer can be programmed to perform a variety of different tasks, the range of applications and environments in which computer systems and other digital devices will be used creates a demand for devices of differing sizes and configurations. Some computer systems are used primarily as servers, in which multiple users (who may be geographically isolated, using a heterogeneous mixture of computer systems and application software) access a centralized set of applications and common database. Other computer systems are used primarily as single-user devices, in which a single user performs a set of applications of interest to the user, locally stores data of interest to the user, and may optionally communicate with other computers as required to access external data. Still other computer systems may perform specialized functions, such as monitoring and controlling physical sensors, switches, motors, valves, and other controls. A special-purpose digital device may or may not even be considered a computer system, but contains many of the design attributes of a general-purpose computer system.
With all the design hierarchies that exist in digital data systems, there is a general need to communicate data among different digital systems or components thereof. Data communication occurs among different digital computer systems, as in the Internet or in a local area network; or among different components of a single digital computer system; or even within the functional elements of a single integrated circuit chip, which is itself part of a larger computer system.
One known technique for supporting data communication among more that two devices is a slotted ring network. A slotted ring network is a packet-based communications network containing a set of point-to-point communication links, each running between of pair of systems, devices, or functional components or subcomponents thereof (herein generally referred to as nodes of the network), the links being arranged to form a ring which includes all the nodes of the network. A node A, wishing to transmit a packet to a node B, transmits the packet to A's immediate neighbor on the ring, which then forwards the packet along the ring, until the packet reaches node B. The network is generally time-multiplexed, so that each packet is transmitted to a next node on the ring during a time interval, and is re-transmitted along the ring in successive time intervals. The capacity of the ring to carry a data packet in such a time interval is referred to as a slot. The ring has a fixed number of slots, each slot traveling around the ring on a pre-determined, fixed schedule. The number of slots may be equal to the number of devices on the ring, or there may be either a greater number or lesser number of slots; e.g., a greater number of slots may be present if the slots delay one or more intervals in some or all of the nodes. A slot may or may not contain a data packet, but travels on the same pre-determined schedule in any case. Arbitration and contention avoidance is relatively simple: if a node wishes to transmit, it waits for a free slot (i.e., one in which there is no packet that needs to be forwarded along the ring from another device), and transmits its packet in the free slot.
Slotted ring networks have the advantage of simple implementation and high utilization without contention. However, one recurring problem with slotted ring networks is starvation. Starvation may occur when a node A transmits a large volume of data to a node B, effectively preventing a node C located between A and B on the network path from transmitting. Starvation in a slotted ring network has been known for some time, and various techniques have been proposed or implemented for dealing with the starvation issue. In general, these techniques involve added complexity and/or may decrease the utilization of the network bandwidth.
It would be desirable to provide improved communications techniques for communicating data among multiple digital devices or components thereof which retain or approach the simplicity and high utilization of a simple slotted ring yet avoid starvation.